package com.zs.letcode.top_interview_questions;

import java.util.HashMap;

/**
 * 直线上最多的点数
 * 给定一个二维平面，平面上有n个点，求最多有多少个点在同一条直线上。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [[1,1],[2,2],[3,3]]
 * 输出: 3
 * 解释:
 * ^
 * |
 * |    o
 * |   o
 * | o
 * +------------->
 * 0 1 2 3  4
 * 示例2:
 * <p>
 * 输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * 输出: 4
 * 解释:
 * ^
 * |
 * |  o
 * | o      o
 * |    o
 * | o       o
 * +------------------->
 * 0 1 2 3 4 5 6
 * 相关标签
 * 哈希表
 * 数学
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/x2n2g1/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/16 11:10
 */
public class Chapter67 {
    public static void main(String[] args) {

    }

    private static class Solution {
        int[][] points;
        int n;
        HashMap<Double, Integer> lines = new HashMap<Double, Integer>();
        int horisontal_lines;

        public Pair<Integer, Integer> add_line(int i, int j, int count, int duplicates) {
            /*
            Add a line passing through i and j points.
            Update max number of points on a line containing point i.
            Update a number of duplicates of i point.
            */
            // rewrite points as coordinates
            int x1 = points[i][0];
            int y1 = points[i][1];
            int x2 = points[j][0];
            int y2 = points[j][1];
            // add a duplicate point
            if ((x1 == x2) && (y1 == y2))
                duplicates++;
                // add a horisontal line : y = const
            else if (y1 == y2) {
                horisontal_lines += 1;
                count = Math.max(horisontal_lines, count);
            }
            // add a line : x = slope * y + c
            // only slope is needed for a hash-map
            // since we always start from the same point
            else {
                double slope = 1.0 * (x1 - x2) / (y1 - y2) + 0.0;
                lines.put(slope, lines.getOrDefault(slope, 1) + 1);
                count = Math.max(lines.get(slope), count);
            }
            return new Pair(count, duplicates);
        }

        public int max_points_on_a_line_containing_point_i(int i) {
    /*
    Compute the max number of points
    for a line containing point i.
    */
            // init lines passing through point i
            lines.clear();
            horisontal_lines = 1;
            // One starts with just one point on a line : point i.
            int count = 1;
            // There is no duplicates of a point i so far.
            int duplicates = 0;

            // Compute lines passing through point i (fixed)
            // and point j (interation).
            // Update in a loop the number of points on a line
            // and the number of duplicates of point i.
            for (int j = i + 1; j < n; j++) {
                Pair<Integer, Integer> p = add_line(i, j, count, duplicates);
                count = p.getKey();
                duplicates = p.getValue();
            }
            return count + duplicates;
        }


        public int maxPoints(int[][] points) {

            this.points = points;
            // If the number of points is less than 3
            // they are all on the same line.
            n = points.length;
            if (n < 3)
                return n;

            int max_count = 1;
            // Compute in a loop a max number of points
            // on a line containing point i.
            for (int i = 0; i < n - 1; i++)
                max_count = Math.max(max_points_on_a_line_containing_point_i(i), max_count);
            return max_count;
        }

        class Pair<K, V> {
            private K key;
            private V value;

            Pair(K key, V value) {
                this.key = key;
                this.value = value;
            }

            public K getKey() {
                return key;
            }

            public void setKey(K key) {
                this.key = key;
            }

            public V getValue() {
                return value;
            }

            public void setValue(V value) {
                this.value = value;
            }
        }
    }
}
